package leetcode_core.leetcode_1;

import org.junit.Test;

public class LongestPalindromeSubseqByOneDesc {
    public int longestPalindromeSubseq(String s) {
        int[] dp = new int[s.length()+5];
        for(int i = 0 ;i<=s.length();i++){
            dp[i] = 1;
        }
        for(int i = s.length()-2;i>=0;i--){
            int pre = 0;
            for(int j = i+1;j<s.length();j++){
                int temp = dp[j];
                if(s.charAt(i) == s.charAt(j)){
                    dp[j] = pre+2;
                }else{
                    dp[j] = Math.max(dp[j],dp[j-1]);
                }
                pre = temp;
            }
        }
        return dp[s.length()-1];
    }

    @Test
    public void test(){
        System.out.println(longestPalindromeSubseq("bbbab"));
        System.out.println(longestPalindromeSubseq("cbbd"));
    }
}
